package com.lyb.sort;

import java.util.Arrays;

/**
 * 插入排序
 */
public class InsertionSort {
    public static void main(String[] args) {
        int[] nums = {4,2,6,1,5,8,3};
        sort(nums);
    }
    public static void sort(int[] nums){
        //外层循环用于控制无序区间的范围，无序区间具体范围是[i,nums.length-1]
        for (int i = 0; i < nums.length; i++) {
            //待插入的元素
            int current = nums[i];
            //从有序区间的最后一个元素开始，与待插入元素进行比较，
            // 若大于待插入元素，则将其向后移动一位，然后继续和前一位进行比较，
            // 直到找到正确的位置，将待插入元素插入即可。
            int j = i - 1;
            while (j >= 0 && nums[j] >= current){
                nums[j + 1] = nums[j];
                j--;
            }
            nums[j+1] = current;
        }
        System.out.println(Arrays.toString(nums));
    }
}
